This invention relates to polygon edge clipping and, more particularly, to clipping edges of a polygon in two dimensions, wherein the resulting clipped edges may be sequentially output without need to store edge values.
In computer image generation (CIG), polygons, or faces, having a predetermined three dimensional spatial relationship are used to represent objects and features of images to be displayed. An example of CIG may be had by reference to U.S. Pat. No. 3,892,051 - Bunker, assigned to the instant assignee.
For objects that are defined in a three-dimensional environment, it is generally necessary to clip or truncate edges of the polygons during some stage of image processing so that an appropriate perspective view may be displayed by a two-dimensional display device, such as a cathode ray tube. A clipping system which clips in three-dimensional space is described in U.S. Pat. No. 3,816,726 - Sutherland et al, while one which clips in two-dimensional space is exemplified by U.S. Pat. No. 3,892,051 - Bunker. The present invention may be considered as more closely related to the one of the Bunker patent, since it is intended to clip in two-dimensional space.
For the system described in the aforementioned U.S. Pat. No. 3,892,051 - Bunker, only face edges that cross a window boundary plane and also intersect a window edge are clipped. All clip points are in the two-dimensional window plane. No attempt is made to close the clipped polygon about the window because the associated display processor only requires left edge information to start displaying a polygon. Faces open to the right are terminated by line reset pulses timed to occur as a line trace coincides with the right edge of the display window. If no left hand start information is available (e.g. polygon larger than the entire display window), then a pseudo-edge coinciding with the left edge boundary of the display window is established for providing a start trace reference.
A method for clipping lines is disclosed in U.S. Pat. No. 3,639,736 - Sutherland, wherein repetitive operations using the mid-point of a line segment determine the portion of the line segment, if any, lying outside a rectangular window.
When clipping to the field of view dictated by a viewpoint and the boundary edges of a view window, it may be necessary to determine boundary edges or portions thereof, that correspond to the top, bottom, left and right side of a square or rectangular view window. Of course, other shaped view windows may be employed and appropriate processing may be determined by one of ordinary skill in the art using the teachings of this application. As described in conjunction with the Bunker patent above, only the left side edge or pseudo-left-edge of a square or rectangular view window was required.
Further, since clipping must be performed in real time for a real-time CIG system that is typically used as a training vehicle, it is desirable to increase the speed at which polygons can be clipped by employing a more efficient method for clipping, such as by avoiding clipping that provides redundant information. An increase in speed of clipping permits more detail per object (resulting in a more realistic image) and/or more objects to be displayed in a scene. Also, it is desirable to sequentially output edge identifiers of the clipped polygon during processing of the original or source polygon, so that store and retrieve cycle times are eliminated.
Accordingly, it is an object of the present invention to provide a method for clipping a polygon in two dimensions wherein the resulting clipped segments may be more rapidly obtained than from known methods.
Another object is to provide a method for clipping a polygon in two dimensions at view window boundary planes wherein the valid portions of all window boundary edges for the resulting clipped figure may be readily determined.
Yet another object is to provide a method for establishing the valid portion of boundary edges of the view window that lie between the edges of a polygon entering and/or exiting the view window without having to calculate the equation of the view window boundary edges.
Still another object is to provide a method for clipping a polygon wherein edges for the resulting clipped figure may be sequentially output as they are determined without having to store all intersection points.